package 中等.模拟;

import java.util.*;

/**
 *
 */
public class O1时间插入删除和获取随机元素_380 {

    public static void main(String[] args) {

        RandomizedSet obj = new RandomizedSet();
        obj.insert(0);
        obj.insert(1);
        obj.remove(0);
        obj.insert(2);
        obj.remove(1);
        System.out.println(obj.getRandom());

    }

}

class RandomizedSet {

    // key用来存值，value用来存value存放于list中对应的索引
    public Map<Integer, Integer> map = new HashMap<>();

    // 如果list不是在末尾，新增或者删除，时间复杂度将不是O(1)
    // list新增的时候默认是在末尾，而删除需要用末尾的值取填充要删除的值，然后将末尾值移除来进行删除
    public List<Integer> list = new ArrayList<>();

    public Random random = new Random();

    public RandomizedSet() {
    }

    public boolean insert(int val) {
        boolean exist = map.containsKey(val);
        if (!exist) {
            list.add(val);
            map.put(val, list.size() - 1);
        }
        return !exist;
    }

    public boolean remove(int val) {
        boolean exist = map.containsKey(val);
        if (exist) {
            Integer lastVal = list.get(list.size() - 1);
            Integer updateIndex = map.get(val);
            list.set(updateIndex, lastVal);
            // 更新最后一个元素的索引
            map.put(lastVal, updateIndex);
            map.remove(val);
            list.remove(list.size() - 1);
        }
        return exist;
    }

    public int getRandom() {
        return list.get(random.nextInt(list.size()));
    }

}